/**
 * Created With IntelliJ IDEA
 * Description:牛客网: 首页 > 试题广场 > 求正数数组的最小不可组成和
 * <a href="https://www.nowcoder.com/questionTerminal/296c2c18037843a7b719cf4c9c0144e4">...</a>
 * User: DELL
 * Data: 2023-04-26
 * Time: 16:34
 */


/**
 * 本题是背包问题的改进版
 * 看这个题解的时候应该先看一下背包问题
 * 背包问题链接:<a href="https://www.nowcoder.com/practice/2820ea076d144b30806e72de5e5d4bbf?tpId=196&tqId=37561&ru=/exam/oj">...</a>
 */
public class Solution {
    /**
     *	解法一
     * 我们将 arr 中的每一个数字 num 看成是重量为 num,且体积也为 num的物体
     * 同时我们将 [min,max]区间中的每一个数 num,看成是背包体积为 num
     * 因此我们就将问题转变为求 背包体积为 n (min<=n<=max)时,背包的重量最多为多大
     * 求出来之后,我们对 dp 数组遍历,找到第一个 dp[i] != i 即背包最大重量不等于背包容量
     * 的,如果有就返回,如果没有,就返回 max+1 即可
     * 具体的状态转移方程背包问题中已经有很详细的了,这里省略.
     * gitee链接:<a href="https://gitee.com/zzurlj/JavaOj/blob/master/knapsack/src/Solution.java">...</a>
     */
    public int getFirstUnFormedNum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        //先求出最大数个最小数
        int min = arr[0];
        int max = 0;
        for (int n : arr) {
            min = Math.min(min,n);
            max += n;
        }
        //状态数组
        int[][] dp = new int[arr.length+1][max+1];
        //数组创建的时候默认为0,不需要初始化
        //状态转移
        for (int i = 1; i <= arr.length; i++) {
            for (int j = min; j <= max; j++) {
                if (arr[i-1] <= j) {
                    dp[i][j] = Math.max(dp[i-1][j-arr[i-1]] + arr[i-1],dp[i-1][j]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        //遍历寻找背包最大重量不等于背包容量的值
        for (int i = min; i <= max; i++) {
            if (dp[arr.length][i] != i) {
                return i;
            }
        }
        return max+1;
    }

    /**
     * 解法二(主要是针对解法一进行优化)
     * 解法一有两个地方可以进行优化
     * 1. 因为 dp 数组每次进行状态转换的时候只和 dp 数组上一行的左边有联系,
     *    因此我们可以进行空间压缩,即创建一个一维数组,每次更新dp数组的时候
     *    从后往前更新,这样子原 dp 数组中存放的就是上一次的值,直接更新即可
     * 2. 原 dp 数组浪费了每一行的前 min 个空间,我们可以加以优化
     *    优化的时候千万要注意转移方程,转移的时候需要分类讨论一下
     */
    public int getFirstUnFormedNum2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        //先求出最大数个最小数
        int min = arr[0];
        int max = 0;
        for (int n : arr) {
            min = Math.min(min,n);
            max += n;
        }
        //状态数组
        int len = max-min+1;
        int[] dp = new int[len];
        //数组创建的时候默认为0,不需要初始化
        //状态转移
        for (int i = 1; i <= arr.length; i++) {
            for (int j = len-1; j >= 0; j--) {
                //这里需要分类讨论
                if (arr[i-1] <= j) {
                    dp[j] = Math.max(dp[j-arr[i-1]] + arr[i-1],dp[j]);
                } else if (arr[i-1] <= j+min) {
                    //这里首先要确保背包可以放得下,即arr[i-1] <= j+min
                    //同时因为如果背包中放入当前物品,则剩余空间已经小于min了
                    //即只有两种情况,即放入该物品且不放入别的物品,或者不放入该物品
                    dp[j] = Math.max(arr[i-1],dp[j]);
                }
                //最后一种情况就是背包放不下的情况,即不用修改dp[j]
            }
        }
        //遍历寻找背包最大重量不等于背包容量的值
        for (int i = 0; i < len; i++) {
            if (dp[i] != i+min) {
                return i+min;
            }
        }
        return max+1;
    }

    /**
     * 解法三
     * 解法三主要是针对解法一和解法二思想上的优化
     * 前两个解法我们的基本思想是求出每一个背包中装入的物品的最大重量,但是题目只是需要我们知道是否可以装满,
     * 因此前两个算法虽然可以解决问题,但是肯定浪费了很多算力,因为求解的问题更复杂了,因此我们接下来对于状态方程dp进行以下优化
     * 状态定义: dp[i][j] 表示的是利用前 i 个数组,可否将背包容量为 j 的包装满
     * 状态转移: 当 arr[i-1] <= j 时: dp[i][j] = dp[i-1][j-arr[i-1]] || dp[i-1][j]
     *         当 arr[i-1] > j 时:   dp[i][j] = dp[i-1][j]
     * 状态初始化: dp[i][0] = true  dp[0][j] = false ,特别注意 dp[0][0] = true
     * 返回值: 从 min -> max 遍历数组,找到第一个不为 true 的下标,返回,若均为 true,就返回 max+1
     * @param arr
     * @return
     */
    public int getFirstUnFormedNum3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        //先求出最大数个最小数
        int min = arr[0];
        int max = 0;
        for (int n : arr) {
            min = Math.min(min,n);
            max += n;
        }
        //状态数组
        boolean[][] dp = new boolean[arr.length+1][max+1];
        //初始化
        for (int i = 0; i <= arr.length; i++) {
            dp[i][0] = true;
        }
        //状态转移
        for (int i = 1; i <= arr.length; i++) {
            for (int j = min; j <= max; j++) {
                if (arr[i-1] <= j) {
                    dp[i][j] = dp[i-1][j-arr[i-1]] || dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        //遍历寻找背包最大重量不等于背包容量的值
        for (int i = min; i <= max; i++) {
            if (!dp[arr.length][i]) {
                return i;
            }
        }
        return max+1;
    }

    /**
     * 解法四
     * 解法四是针对解法三的优化,优化的也是两个浪费空间的地方
     * 1. 因为 dp 数组每次进行状态转换的时候只和 dp 数组上一行的左边有联系,
     *    因此我们可以进行空间压缩,即创建一个一维数组,每次更新dp数组的时候
     *    从后往前更新,这样子原 dp 数组中存放的就是上一次的值,直接更新即可
     * 2. 原 dp 数组浪费了每一行的前 min 个空间,我们可以加以优化
     *    优化的时候千万要注意转移方程,转移的时候需要分类讨论一下
     * @param arr
     * @return
     */
    public int getFirstUnFormedNum4(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        //先求出最大数个最小数
        int min = arr[0];
        int max = 0;
        for (int n : arr) {
            min = Math.min(min,n);
            max += n;
        }
        //状态数组
        int len = max-min+1;
        boolean[] dp = new boolean[len];
        //初始化
        //状态转移
        for (int i = 1; i <= arr.length; i++) {
            for (int j = len-1; j >= 0; j--) {
                if (arr[i-1] <= j) {
                    //这个情况呀我们可以基于当前dp数组直接进行状态转移
                    dp[j] = dp[j-arr[i-1]] || dp[j];
                } else if (arr[i-1] == j + min) {
                    //这个情况是当前背包正好可以放入当前数字
                    dp[j] = true;
                }
                //剩余情况均不可能用当前数字将当前背包放满,因此dp不用改变
            }
        }
        //遍历寻找背包最大重量不等于背包容量的值
        for (int i = 0; i < len; i++) {
            if (!dp[i]) {
                return i+min;
            }
        }
        return max+1;
    }
}
